import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    // 两数之和

    // 流氓解法
    public int getSum1(int a, int b) {
        return a+b;
    }

    // 模拟加法运算
    public int getSum(int a, int b) {
        do {
            // 1、计算无进位相加的结果
            int temp = a ^ b;
            // 2、计算进位的结果
            b = (a & b) << 1;
            a = temp;
        } while (b != 0);
        return a;
    }

    // 只出现一次的数字II
    public int singleNumber1(int[] nums) {
        // 哈希表遍历记录
        Map<Integer, Integer> hash = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            hash.put(nums[i], hash.getOrDefault(nums[i], 0)+1);
        }
        for (int i = 0; i < nums.length; i++) {
            if (hash.get(nums[i]) == 1) {
                return nums[i];
            }
        }
        return -1;
    }

    public int singleNumber(int[] nums) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            // 计算某一个比特位上的和
            int sum = 0;
            for (int j = 0; j < nums.length; j++) {
                sum += ((nums[j] >> i) & 1);
            }
            sum %= 3;
            ret |= (sum << i);
        }
        return ret;
    }


    // 消失的两个数字
    public int[] missingTwo1(int[] nums) {
        // 哈希表遍历统计
        int n = nums.length;
        int[] hash = new int[n + 3]; // 0+缺失的两个空间
        int[] ret = new int[2];
        for (int x : nums) {
            hash[x]++;
        }
        int j = 0;
        for (int i = 1; i < n + 3; i++) {
            if (hash[i] == 0) {
                ret[j++] = i;
            }
        }
        return ret;
    }


    public static int[] missingTwoError(int[] nums) {
        // 先找到分组的依据
        int n = nums.length;
        int sum = 0;
        for (int i = 1; i < n+3; i++) {
            sum ^= i;
        }
        for (int i = 0; i < n; i++) {
            sum ^= nums[i];
        }
        // 找到最右边的1，作为分组的依据
        int mask = sum & (-sum);
        // 将 mask 作为分组的依据
        int[] ret = new int[2];
        for (int i = 1; i < n+3; i++) {
            if ((mask & i) != 0) {
                ret[0] ^= i;
            } else {
                ret[1] ^= i;
            }
        }
        for (int i = 0; i < n; i++) {
            if ((nums[i] & mask) != 0) { // 这里不一定是1
                ret[0] ^= nums[i];
            } else {
                ret[1] ^= nums[i];
            }
        }
        return ret;
    }

    public static int[] missingTwo(int[] nums) {
        // 先找到分组的依据
        int n = nums.length;
        int sum = 0;
        for (int i = 1; i < n+3; i++) {
            sum ^= i;
        }
        for (int i = 0; i < n; i++) {
            sum ^= nums[i];
        }
        // 找到最右边的1，作为分组的依据
        int mask = 0;
        for (int i = 0; i < 32; i++) {
            if (((sum >> i) & 1) == 1) {
                mask = i;
                break;
            }
        }
        // 将 mask 作为分组的依据
        int[] ret = new int[2];
        for (int i = 1; i < n+3; i++) {
            if (((i>>mask) & 1) == 1) {
                ret[0] ^= i;
            } else {
                ret[1] ^= i;
            }
        }
        for (int i = 0; i < n; i++) {
            if (((nums[i] >> mask) & 1) == 1) {
                ret[0] ^= nums[i];
            } else {
                ret[1] ^= nums[i];
            }
        }
        return ret;
    }


    public static void main(String[] args) {
        // 上面两个代码都是正确的
        System.out.println(Arrays.toString(missingTwoError(new int[]{3})));
        System.out.println(Arrays.toString(missingTwo(new int[]{3})));
    }

}